#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
//删除并获得点数：https://leetcode.cn/problems/delete-and-earn/
using namespace std;
class Solution {
public:
    //将数组预处理，之后等价于打家劫舍问题
    int deleteAndEarn(vector<int>& nums) {
        //预处理原数组
        int n=nums.size();
        int max_num=INT_MIN;
        for(int i=0;i<n;i++) max_num=max(max_num,nums[i]);
        int len=max_num+1;
        vector<int> arr(len,0);
        for(int i=0;i<n;i++) arr[nums[i]]+=nums[i];

        //打家劫舍问题
        vector<int> f(len);
        auto g=f;
        f[0]=arr[0],g[0]=0;
        for(int i=1;i<len;i++)
        {
            f[i]=g[i-1]+arr[i];
            g[i]=max(f[i-1],g[i-1]);
        }
        return max(f[len-1],g[len-1]);
    }
};